The behavior of many common items and situations can be modeled using a simple but powerful tool called a finite state machine (FSM). Examples of functions that have been efficiently translated into state machines include vector control for signal processing algorithms, data encoding and decoding, encryption and decryption, event monitoring, and simple machine control functions. An FSM is usually represented in the form of a directed graph that includes states interconnected by transitions. Many computer tools exist that enable designers to “draw” a representation of the system being modeled by defining states of a state machine and connecting those states together with directional lines that represent state transitions. Such a model is generally independent of the system being modeled and can be created before or after the physical system is developed.
An FSM is, generally, a digital (or sometimes mechanical) device that traverses through a sequence of states in an orderly fashion, with the transition from one state to another representing the consumption of one or more inputs or occurrence of other events. In some cases, state transitions are augmented with various activities. The FSM may be embodied as a set of computer-readable instructions that a computer processor can read and follow, and/or a collection of logic gates for implementing particular operations.
A state machine will typically include two distinct functional blocks: a next state decoder and an output decoder. The next state decoder determines the next state of the state machine (i.e., based on the current state and a set of inputs) while the output decoder generates the actual outputs. It is the next state decoder that is responsible for ensuring that the state machine traverses an order of states, as directed by the inputs; while the output decoder provides sequences of output signals based upon the state transitions. At times, these outputs may be returned as inputs to the FSM, e.g., via one or more feedback signals.
The distinguishing characteristic of a state machine then is its process-oriented nature. The state machine moves over time from state to state, or put differently, from milestone to milestone, to an ultimate goal or final state. State machines are typically lossless in their processing. That is, they consume their input in order and without any losses. This assumption is reasonable in many domains, but not all. In particular, when a state machine's input is a series of data items provided by multiple systems in a distributed architecture, ordering may be subverted, and data may be lost. In such situations conventional state machines either stall or make incorrect state transitions; each outcome being unacceptable. Accordingly, what is needed is a state machine capable of coping with situations in which input data may arrive out of sequence or not at all without experiencing such errors.